#include <stdio.h>

// 斐波那契数底层满足: 当数位为0,数为0 当数位为1,数为1 这两种是分解之后的最简单状况
// 使用分治的思想,在求斐波那契数的时候我们可以将所有情况分为 得数 = 上一项的数字 + 上上一项的数字
// 然后就可以一直分开,直到所求的数字为底层的0和1

int non_fibonacci (int num) // 这是使用了非递归的方式解决的
{

    int array [num + 1] ;

    array [0] = 0 , array [1] = 1 ;

    for (int i = 2 ; i <= num ; i++)
    {

        array [i] = array [i - 2] + array [i - 1] ; // 建一个数组,使用数组计算

    }

    return array [num] ;

}

int is_fibonacci (int num) // 这是使用了递归的方式去解决的
{

    if (num == 0) // 如果num在递归里面为零了,停止递归返回值
    {

        return 0 ;

    }

    else if (num == 1) // 如果
    {

        return 1 ;

    }

    else
    {

        return is_fibonacci (num - 1) + is_fibonacci (num - 2) ;

    }

}

int main ()
{

    int get1 = 0 , get2 = 0 ;

    int num = 0 ;

    scanf ("%d" , &num) ;

    // 使用非递归的方式

    get1 = non_fibonacci (num) ;

    printf ("使用非递归的方式求得的第%d个的斐波那契数为: %d\n" , num , get1) ;

    // 使用递归的方式

    get2 = is_fibonacci (num) ;

    printf ("使用递归的方式求得的第%d个的斐波那契数为: %d\n" , num , get2) ;

    return 0 ;

}